// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _274

func hIndex(citations []int) int {
	n := len(citations)
	buckets := make([]int, n+1)
	for _, c := range citations {
		buckets[min(c, n)]++
	}

	sum := 0
	for i := n; i >= 0; i-- {
		sum += buckets[i]
		if sum >= i {
			// i = 0 时，必有 sum == i
			return i
		}
	}

	return -1 // unreachable
}

// 题目的意思就是给你一个数组，求一个最大的h，使得数组中至少有h个数都大于等于h
//
// 那就搞个大小为n+1的桶来存放每个数出现的次数，超过数组长度的数也放到数组长度所对应下标的值中
// 比如：3 0 6 1 5
// len=5 => buckets[5] =>
// 1 1 0 1 0 2
// 0 1 2 3 4 5
// 然后从后往前遍历这个桶，将他们的值加起来，如果加一起的值大于等于当前下标就返回
// 下标5，值为2，没有超过，继续
// 下标4，值为2，没有超过，继续
// 下标3，值为2+1=3，大于等于当前下标，返回3，即至少有3个数是大于等于3的
//
// 再看示例2
// 1 3 1
// buckets[3]
// 0 2 0 1
// 0 1 2 3
// 下标3，值为1，没有超过，继续
// 下标2，值为1，没有超过，继续
// 下标1，值为1+2=3，超过了，返回1，即至少有1个数是大于等于1的
